package com.cqs.leetcode.search;

import java.util.ArrayList;

public class Searcha2DMatrixII240 {
    static class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
            for (int i = 0; i < matrix.length; i++) {
                if (matrix[i][0] < target) {
                    int left = 0, right = matrix[i].length - 1;
                    while (left <= right) {
                        int mid = (left + right) / 2;
                        if (matrix[i][mid] == target) return true;
                        if (matrix[i][mid] > target) right = mid - 1;
                        else left = mid + 1;
                    }
                }else {
                    return matrix[i][0] == target;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        ArrayList<int[][]> cases = new ArrayList<>();
        cases.add(new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}});

        cases.forEach(it -> {
            System.out.println(it[1][3]);
            System.out.println(s.searchMatrix(it, 50));
        });
    }
}
